'''
@Descripttion: 
@version: 
@encoding: utf-8
@Author: qiurongcan
Date: 2025-09-08 10:56:34
LastEditTime: 2025-09-08 12:19:07
'''
# 最长有效括号


class Solution:
    def longestValidParentheses(self, s):

        n = len(s)
        if n == 0:
            return 0
        
        # dp 用来记录需要跳过的长度
        dp = [0] * n
        res = 0
        for i in range(n):
            if i > 0 and s[i] == ")":
                if s[i - 1] == "(":
                    dp[i] = dp[i - 2] + 2
            
                elif s[i - 1] == ")" and i - dp[i - 1] - 1 >= 0 and s[i - dp[i - 1] - 1] == "(":
                    dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]
                
                if dp[i] > res:
                    res = dp[i]

        
        return res




